package com.zjj.algorithm.learning.atguigu.sort;

import java.util.Arrays;

/**
 * 插入排序
 * 算法描述
 * 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
 * <p>
 * 1、从第一个元素开始，该元素可以认为已经被排序；
 * 2、取出下一个元素，在已经排序的元素序列中从后向前扫描；
 * 3、如果该元素（已排序）大于新元素，将该元素移到下一位置；
 * 4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
 * 5、将新元素插入到该位置后；
 * 6、重复步骤2~5。
 * <p>
 * 使用选择排序，排 80000 个数据，用时 573 ms
 *
 * @author zjj_admin
 * @date 2022/11/13 19:46
 */
public class InsertionSort {

    public static void main(String[] args) {

        int[] array = new int[]{2, 3, 1, 2, 4, 3};
        insertionSort(array);
        System.out.println("array = " + Arrays.toString(array));

        //测试排 80000 个数据用时
//        int[] arr = new int[80000];
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random() * 800000);
//        }
//        long time1 = System.currentTimeMillis();
//
//        insertionSort(arr);
//        long time2 = System.currentTimeMillis();
//        System.out.printf("使用选择排序，排 %d 个数据，用时 %s ms", arr.length, (time2 - time1));

    }

    public static void insertionSort(int[] array) {

        int insertValue;
        int insertIndex;
        for (int i = 1; i < array.length; i++) {
            insertValue = array[i];
            insertIndex = i - 1;
            while (insertIndex >= 0 && insertValue < array[insertIndex]) {
                array[insertIndex + 1] = array[insertIndex];
                insertIndex--;
            }
            array[insertIndex + 1] = insertValue;
//            System.out.printf("第 %d 次排序：%s \n" ,i, Arrays.toString(array));
        }

    }
}
